/* 
 * File:   ApproximanteMedian.h
 * Author: karthik
 *
 * Finds approximate median using histograms and paper "An Efficient Algorithm for the
 * Approximate Median Selection Problem"
 *
 * Created on November 18, 2011, 12:27 PM
 */

#ifndef _APPROXIMATEMEDIAN_H
#define	_APPROXIMATEMEDIAN_H

#include <cmath>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

class ApproximateMedian{
    //total number of records in data
    int totalrecords;
    //total number of dimensions
    int D;
    //pointer to an array, to hold computed median value accross each dimension
    double *mpi;
    //pointer to hold address of array values for a two dimensional data
    double* array_data;
    //pointer to two dimensional arrays, that holds the actual data
    double** data;

public:

    ApproximateMedian();

    ApproximateMedian(int d);
    //Constructor for ApproxiMedian class
    //Takes total number of records (tr) and total number of dimensions (d) as input and
    //assigns number of dimensions to variables
    ApproximateMedian(int tr, int d);
    //A function to intialize variables
    void initialize(int tr, int d, double **val);
    //A function to assign data
    void set_data(double **d);
    //A function to find approximate median, by using histogram. Function assumes, data value is in range 0.0-1.0
    //Calculates approximate median value in each dimension, by binning the data records in each dimension
    double* findapproximatemedians();
    //A function that performs data transformation, based on Pyramid Technique paper
    //See paper, for details
    double* convertdatapoint(double values[]);
    //A function that performs query transformation, based on Pyramid Technique paper
    //See paper, for details
    double ** convertqueryrange(double q[][2]);
    //This function moves the median of a triplet of terms at location A[i],
    //A[j], A[k] to the middle position
    void triplet_adjust(double A[], int i, int Step);
    //This function sorts Size elements of the array A located at positions Left, Left+Step,
    //Left+2*Step.....
    void selection_sort(double A[], int Left, int Size, int Step);
    //This function returns the approximate median of the array A[0,...,Size-1]
    double approximate_median_anyN(double A[], int Size);
    //A function to calculated median for each dimension in the given data
    //using function approximate_median_anyN
    double* findapproximatemediansusingAMN();

    void set(int i, double value);

    double * findmedian();

    double getmedian(int d);

    void setmedian(double *m);

};


#endif	/* _APPROXIMATEMEDIAN_H */

